package com.lx.algorithm.code.xly3.class04;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2022-01-10 15:11:26
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2022-01-10     张李鑫                     1.0         1.0 Version
 */
public class Code02 {

    /**
     * 双向链表节点结构和二叉树节点结构是一样的，如果你把last认为是left，next认为是next的话。
     * 给定一个搜索二叉树的头节点head，请转化成一条有序的双向链表，并返回链表的头节点。
     */

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static class Info {
        Node left;
        Node right;

        public Info(Node left, Node right) {
            this.left = left;
            this.right = right;
        }
    }

    public static Node change(Node node) {
        if (node == null) {
            return null;
        }
        return process(node).left;
    }

    private static Info process(Node node) {
        if (node == null) {
            return new Info(null, null);
        }
        Info leftInfo = process(node.left);
        if (leftInfo.right != null) {
            leftInfo.right.right = node;
        }
        node.left = leftInfo.right;

        Info rightInfo = process(node.right);
        node.right = rightInfo.left;

        if (rightInfo.left != null) {
            rightInfo.left.left = node;
        }

        Node left = leftInfo.left == null ? node : leftInfo.left;
        Node right = rightInfo.right == null ? node : rightInfo.right;

        return new Info(left, right);
    }

    public static void main(String[] args) {
        Node head = new Node(5);
        head.left = new Node(2);
        head.right = new Node(9);
        head.left.left = new Node(1);
        head.left.right = new Node(3);
        head.left.right.right = new Node(4);
        head.right.left = new Node(7);
        head.right.right = new Node(10);
        head.left.left = new Node(1);
        head.right.left.left = new Node(6);
        head.right.left.right = new Node(8);

        Node change = change(head);

        Node cur=change;
        while (change.right!=null){
            System.out.println(cur.value);
            cur=cur.right;
        }

    }
}
